package NO3_LinkedList;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 2025-09-10
 * 力扣 - 148. 排序链表
 * <p>
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 */
public class SortListMain {
    public static void main(String[] args) {
        ListNode head = new ListNode(4,
                new ListNode(2,
                        new ListNode(1,
                                new ListNode(3))));
        ListNode.printList(sortList(head));
    }

    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 1. 收集节点值
        List<Integer> values = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            values.add(current.val);
            current = current.next;
        }

        // 2. 排序值
        Collections.sort(values);

        // 3. 重用原节点，只修改值
        current = head;
        int index = 0;
        while (current != null) {
            current.val = values.get(index++);
            current = current.next;
        }

        return head;  // 返回原链表头
    }

    // 优解
    public static ListNode sortList1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 找到中点
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 分割链表
        ListNode rightHead = slow.next;
        slow.next = null;

        // 递归排序
        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);

        // 合并有序链表
        return merge(left, right);
    }

    private static ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        current.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}
